#include <bits/stdc++.h>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    // void traverse(TreeNode *cur, vector<int> &res)
    // {
    //     if (cur == nullptr)
    //     {
    //         return;
    //     }
    //     traverse(cur->left, res);
    //     res.push_back(cur->val);
    //     traverse(cur->right, res);
    // }

    // vector<int> inorderTraversal(TreeNode *root)
    // {
    //     vector<int> res;
    //     traverse(root, res);
    //     return res;
    // }
    // vector<int> inorderTraversal(TreeNode *root)
    // {
    //     stack<TreeNode *> stk;
    //     vector<int> res;
    //     TreeNode *cur = root;
    //     while (!stk.empty() || cur != nullptr)
    //     {
    //         if (cur != nullptr)
    //         {
    //             stk.push(cur);
    //             cur = cur->left;
    //         }
    //         else
    //         {
    //             cur = stk.top();
    //             stk.pop();
    //             res.push_back(cur->val);
    //             cur = cur->right;
    //         }
    //     }
    //     return res;
    // }
    vector<int> inorderTraversal(TreeNode *root)
    {
        stack<TreeNode *> stk;
        vector<int> res;
        if (root != nullptr)
        {
            stk.push(root);
        }
        while (!stk.empty())
        {
            TreeNode *cur = stk.top();
            if (cur != nullptr)
            {
                stk.pop();
                if (cur->right)
                {
                    stk.push(cur->right);
                }
                stk.push(cur);
                stk.push(nullptr);
                if (cur->left)
                {
                    stk.push(cur->left);
                }
            }
            else
            {
                stk.pop();
                cur = stk.top();
                stk.pop();
                res.push_back(cur->val);
            }
        }
        return res;
    }
};

int main()
{
    TreeNode *node = new TreeNode(1);
    TreeNode *node1 = new TreeNode(2);
    TreeNode *node2 = new TreeNode(3);
    node->left = node1;
    node->right = node2;
    Solution sol;
    vector<int> res = sol.inorderTraversal(node);
    for (auto num : res)
    {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}
